import javax.swing.plaf.IconUIResource;

public class Solution {
    public class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }
    //    链表的属性，头节点
    public MySingleList.ListNode head;
    public void createList(){
        Solution.ListNode node1 = new Solution.ListNode(1);
        Solution.ListNode node2 = new Solution.ListNode(2);
        Solution.ListNode node3 = new Solution.ListNode(3);
        Solution.ListNode node4 = new Solution.ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

    }

    public ListNode reverseList1(ListNode head) {
        if (head == null){
            return head;
        }
        if (head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = pre.next;
        ListNode be = cur.next;
        head.next = null;
        while(cur != null){
            cur.next = pre;
            pre = cur;
            cur = be;
            /*在这里会出现空指针异常*/
            be = be.next;
        }
        return cur;
    }

    public ListNode reverseList(ListNode head) {
    /*利用头插法*/
//        ListNode cur = head.next;
//        if (head == null){
//            return null;
//        }
//        if (head.next == null){
//            return head;
//        }
//        while(cur != null){
//            ListNode curNext = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = curNext;
//        }
//        return head;
        if(head==null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public ListNode findKeyToTail(ListNode head, int k){
        if (head==null){
            return null;
        }
        if (k <= 0 ) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        int cuont = 0;
        while(cuont != k-1){
//            还没走完k-1步，发现fast.next==null
            if (fast.next != null){
                fast = fast.next;
                cuont++;
            }else {
                return null;
            }
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null){
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode node = newHead;
        while(list1 != null && list2 != null){
            if (list1.val < list2.val){
                newHead.next = list1;
                list1 = list1.next;
            }else {
                newHead.next = list2;
                list2 = list2.next;
            }
            newHead = newHead.next;
        }
        if (list1 == null){
            newHead.next = list2;
        }
        if (list2 == null){
            newHead.next = list1;
        }
        return node.next;
    }

//    判断是否是回文
    public boolean chkPalindrome(ListNode head){
//        1.找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
//        2.翻转
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
//        一个向前一个向后
        while(slow != head ){
            if (slow.val != head.val){
                return false;
            }
//            偶数情况
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    /*
    * 输入两个链表找公共节点
    * */
    public ListNode find(ListNode headA,ListNode headB){
        int sizeA = size(headA);
        int sizeB = size(headB);
        int len = 0;
        ListNode cur = null;
        if (sizeA > sizeB){
            len = sizeA - sizeB;
            while(len != 0){
                cur = headA;
                len--;
            }
        }else {
            len = sizeB - sizeA;
        }
        return null;
    }
    private int size(ListNode head){
        int size = 0;
        while(head != null){
            size++;
            head = head.next;
        }
        return size;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        int lenA = 0;
        int lenB = 0;
//        永远指向最长的链表
        ListNode pl = headA;
//        永远指向最短的链表
        ListNode ps = headB;
//        分别求长度
        while (pl != null){
            lenA++;
            pl = pl.next;
        }
        while( ps != null){
            lenB++;
            ps = ps.next;
        }
//        结点归位
        pl = headA;
        ps = headB;
        int len = lenA-lenB;
        if (len > 0 ){
            pl = headB;
            ps = headB;
            len = lenB - lenA;
        }
//        保证pl指向最长的 ps指向最短的 len一定是正数
//        让pl走len步
        while(len != 0){
            pl = pl.next;
            len--;
        }
//      一人一步
        while(pl != null && ps != null && pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

    public boolean hasCycle(ListNode head){
        if (head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
//        slow走一步，fast走两步，最多错过一圈就相遇
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
}
